package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author: ZhouBert
 * @date: 2021/2/9
 * @description: 71. 简化路径
 * https://leetcode-cn.com/problems/simplify-path/
 */
public class B_71_简化路径 {

	public static void main(String[] args) {
		B_71_简化路径 action = new B_71_简化路径();
		test1(action);
		test2(action);
		test3(action);
		test4(action);
		test5(action);
		test6(action);
	}


	public static void test1(B_71_简化路径 action) {
		//	/home
		String path = "/home/";
		String res = action.simplifyPath(path);
		System.out.println("res = " + res);
	}

	public static void test2(B_71_简化路径 action) {
		//	/
		String path = "/../";
		String res = action.simplifyPath(path);
		System.out.println("res = " + res);
	}

	public static void test3(B_71_简化路径 action) {
		//	/home/foo
		String path = "/home//foo/";
		String res = action.simplifyPath(path);
		System.out.println("res = " + res);
	}

	public static void test4(B_71_简化路径 action) {
		//	/c
		String path = "/a/./b/../../c/";
		String res = action.simplifyPath(path);
		System.out.println("res = " + res);
	}

	public static void test5(B_71_简化路径 action) {
		//	/a/b/c
		String path = "/a//b////c/d//././/..";
		String res = action.simplifyPath(path);
		System.out.println("res = " + res);
	}

	public static void test6(B_71_简化路径 action) {
		//	/
		String path = "/..//";
		String res = action.simplifyPath(path);
		System.out.println("res = " + res);
	}



	/**
	 * 跟 X缀表达式 的转换非常接近
	 * 由于 path 是一个绝对路径，说明是以 / 开头的
	 * --
	 * 由于最后所求的跟 index 无关，不像 {@link C_84_柱状图中最大的矩形} 中 width 是跟 index 有关联的，
	 * 所以需要保留 index
	 * --
	 * 我写的太复杂了，需要讨论的太多了！
	 * 看了下题解，可以通过 / 这个特殊符号中最特殊的符号来利用，通过其进行分隔，再进行分段处理。
	 * @param path
	 * @return
	 */
	public String simplifyPath(String path) {
		char[] chars = path.toCharArray();
		int len = chars.length;
		//由于最后所求的跟 index 无关，所以用 character 来存储
		Deque<Character> stack = new ArrayDeque<>();
		//使用 label 来判断 /. or /.. 的情况
		//when /.-> label =1; /.. -> label = 2; /... -> label = 3
		int label = 0;
		for (int i = 0; i < len; i++) {
			if (stack.isEmpty()) {
				stack.addLast(chars[i]);
				continue;
			}
			if (chars[i] == '/') {
				//当 当前为 '/' 时，需要处理多个情况
				if (stack.peekLast() == '/') {
					//1.先处理多个 / 的情况
					do {
						i++;
					} while (i < len && chars[i] == '/');
					if (i == len) {
						//此时已经遍历完毕
						//-> 将栈顶元素 remove 即可
						stack.removeLast();
						break;
					}
					//此时终于找到了非 '/' 的元素
					i--;
					continue;
				}
				// now 栈顶非 '/'
				if (label == 1) {
					//now 处理[当前目录]
					stack.removeLast();
				} else if (label == 2) {
					//now 处理[上一级]
					//一直弹出直到栈顶元素为 '/'
					while (stack.removeLast() != '/') {
					}
					if (stack.isEmpty()) {
						stack.addLast('/');
						continue;
					}
					while (stack.peekLast() != '/') {
						stack.removeLast();
					}
				} else {
					stack.addLast('/');
				}
				label = 0;
				continue;
			}
			if (chars[i] == '.') {
				//表示当前目录
				//但是得看之前是啥情况
				//-> 先看一眼栈顶，再判断 label 的情况
				if (stack.peekLast() == '/') {
					label = 1;
					stack.addLast('.');
					continue;
				}
				//此时 栈顶元素非 '/'
				if (stack.peekLast() != '.') {
					stack.addLast('.');
					//需要保证处理了以后 label  == 0
					continue;
				}
				//此时 栈顶元素 == '.'
				if (label == 0) {
					//说明前面木有 /
					//-> 只是当成 普通的目录名称
				} else if (label == 1) {
					//说明已经是 '/.'
					label = 2;
					//此时 '/..'
				} else {
					//如果前面已经 '/..'
					//那么就是普通的文件夹了
					label = 0;
					//将标志恢复到目录的状态
				}
				stack.addLast('.');
				continue;
			}
			//此时就是普通的字符
			stack.addLast(chars[i]);
			label = 0;
		}
		if (stack.isEmpty()){
			return "/";
		}
		//如果遍历完毕但是 label != 0
		if (label == 1) {
			stack.removeLast();
		} else if (label == 2) {
			while (stack.removeLast() != '/') {
			}
			if (stack.isEmpty()) {
				stack.addLast('/');
			}
			while (stack.peekLast() != '/') {
				stack.removeLast();
			}
		}


		if (stack.peekLast() == '/' && stack.size() > 1) {
			stack.removeLast();
		}
		//最后已经简化完毕，可以将 stack 中的元素倒出来
		char[] res = new char[stack.size()];
		for (int i = stack.size() - 1; i >= 0; i--) {
			res[i] = stack.removeLast();
		}
		return new String(res);
	}
}
